import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=354 lang=java
 *
 * [354] 俄罗斯套娃信封问题
 */

// @lc code=start
class Solution {
    // 这个月又是dp月噢
    // 这个东西和300-最长增长子序列有点像,借用它的思路
    // 先对宽度排序，确保
    public int maxEnvelopes(int[][] envelopes) {
        int len = envelopes.length;
        int[] dp = new int[len];//用来存

        Arrays.sort(envelopes,(e1,e2)->{//lamda表达式，实现comparator
            if(e1[0] == e2[0]) return e1[1]-e2[1];
            else return e1[0]-e2[0];
        });
        
        int res = 0;
        for(int i = 0;i<len;i++){
            dp[i] = 1;
            for(int j = 0 ;j<i ;j++){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    //满足套娃条件
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            res=Math.max(dp[i], res);
        }
        return res;
    }

}
// @lc code=end

